Points-to analyses do not store the justification, or provenance for the presence of a tuple in the points-to result. However, in some contexts client-driven queries may require such justification, typically for specific points-to tuples (e.g., during debugging) that may satisfy a given property. For example, a code analysis may check whether a potentially tainted variable may be used at a given point in a program. The provenance for the relevant points-to tuples would identify the source of the potentially tainted variable and the sequence of assignments and method calls that may result in the potentially tainted object reaching the point in the program. However, it is not obvious how to combine provenance information for a client-driven analysis with bottom-up computation of results. During bottom-up processing, it is unclear which tuples will be relevant to the client query and therefore provenance information for all values may need to be tracked. And using a top-down algorithm is impractical because it requires substantial changes to the existing infrastructure. In addition, it is desirable for any provenance generating algorithm to be efficient, in order to scale to large codebases.